package com.example.leetcode.prcatice;

import java.util.HashMap;

/**
 * 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 输入：points =
 * [[1,1],[2,2],[3,3]] 输出：3 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出：4
 */
public class Test149 {

    public int maxPoints(int[][] points) {
        if(points.length<3){
            return points.length;
        }

        int res = 0;
        // 遍历每一个点 利用斜率
        for (int i =0;i<points.length;i++){
            int repeat = 0;  //重复的点
            int max = 0; // 记录当前点经过的最大值
            HashMap<String, Integer> map = new HashMap<>();
            for (int j = i+1;j<points.length;j++){
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if(x == 0 & y==0){
                    repeat++;  // 说明是一个点
                    continue;
                }
                int reduction = reduction(x, y);// 约分
                x = x / reduction;
                y = y / reduction;
                String key = x+"-"+y;
                map.put(key,map.getOrDefault(key,0)+1); // 判断这个key是否含有，如果没有就为1
                max = Math.max(max,map.get(key));
            }
            res = Math.max(res,max+repeat+1); // 加上重复点和当前点
        }
        return res;
    }



    public int reduction(int x , int y){
        while (y != 0){
            int temp = x % y;
            x = y;
            y = temp;
        }
        return x;
    }
}
class Demo149{
  public static void main(String[] args) {
    Test149 t = new Test149();
    int[][]points = {{1,1},{2,2},{3,3}};
    System.out.println(t.maxPoints(points));
  }
}